package Interview.Amazon;

/**
 * 数组有N-2个数字，数字的范围为1 ... N，没有重复的元素，要求打印缺少的2个数字, 空间复杂度O（1）
 * @Auther: leiwenkang
 * @Date: 2020/7/26 18:23
 * @Description:
 */
public class Test03打印数组中缺少的两个数字 {
    public static void main(String[] args) {
        int[] array = {5, 7, 2, 4, 9, 6, 1};
        printLossNum(array, 9);
    }

    //数学公式，只能解决2个数的缺失情况
    //https://blog.csdn.net/yangyingda2008/article/details/84609128?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase
    //先计算a + b的值
    //再计算a^2 + b^2的值
    //根据这两个公式，则可以算出a和b的值。具体计算，可以先计算出(a-b)^2的值，从而计算得到a-b的值。
    public static void printLossNum(int[] array, int N) {
        if (array == null || array.length == 0) {
            return;
        }
        //计算1+2+...+N的值
        int sum  = N * (N + 1) >> 1;
        int squareSum = sum * (2 * N + 1) / 3;
        for (int i = 0; i < array.length; i++) {
            sum -= array[i];
            squareSum -= array[i] * array[i];
        }

        int ASubB = (int)Math.sqrt(2 * squareSum - sum * sum);
        System.out.println(((sum + ASubB) >> 1) + " and " + ((sum - ASubB) >> 1));
    }
}